Many communication networks include an arrangement in which a centralized node, or “hub,” communicates with a group of non-centralized terminals, which are here referred to as “remote terminals.” If the remote terminals communicate with the hub over a common channel, it is possible for the communications between one remote terminal and the hub to interfere with communications between other remote terminals and the hub. To prevent such interference, it is often desirable to employ the techniques of time-division multiplexing. According to such techniques, each remote terminal has an assigned timeslot during which it may communicate with the hub by sending or receiving transmissions without interference from competing remote terminals within the group.
In some fields, the process of determining which remote terminal should be assigned a given timeslot is referred to as “scheduling.” That terminology will be adopted here. Similarly, an entity, typically resident at the hub, that makes the scheduling determination for each timeslot will be referred to here as a “scheduler.”
The simplest form of scheduling is “round robin” scheduling, in which the remote terminals are scheduled in a fixed order, and typically for equal durations. The scheduler repeatedly cycles through the remote terminals in the fixed order.
Although useful, round robin scheduling suffers from certain drawbacks. One such drawback is conveniently described with reference to the specific case of forward, or “downlink,” transmissions from a base station to mobile stations of a cellular network.
The maximum rate at which a mobile station can receive data from the base station, without exceeding a given error rate, is limited by interference and noise, and by the received signal strength at the current location of the mobile station. Typically, the ratio of signal strength to the combined noise and interference, often referred to as the “signal to interference plus noise ratio” SINR, is greatest near the center of a cell and lowest near the margins of the cell. The SINR also fluctuates over time.
At any given time, then, some mobile stations will be able to receive data at higher rates than others. By favoring those mobile stations having the highest SINR for receiving downlink transmissions, the scheduler can drive up the throughput of the system; i.e., the long-term average amount of downlink data transmitted per unit time.
If, for example, the revenue collected by the network operator depends upon throughput, it is desirable to drive the throughput as high as possible. However, a scheduler that always favors those mobiles having the highest SINR will tend to deny service to mobiles having low SINR. As a consequence, users will experience intolerable service interruptions, and will be dissatisfied.
Those skilled in the art have recognized the need to balance throughput against “fairness;” i.e., against the need to assure that service to each mobile station, or other remote terminal, is scheduled often enough to satisfy all of the users.
This necessity is discussed, for example, in U.S. Pat. No. 6,229,795, which issued on May 8, 2001 to R. Pankaj et al. (the '795 patent). The '795 patent describes a cellular system for high-rate packet-data transmission, in which the downlink has a variable rate of data transmission. The scheduling of individual remote terminals is based on a weight assigned to each remote terminal. At the base station, a scheduler uses these weights to make scheduling decisions. A scheduling algorithm is used that aims to balance the competing objectives of throughput and fairness.
According to that algorithm described in the '795 patent, a threshold is computed by averaging the instantaneous downlink data-transmission rates for all mobile stations that have queued data waiting at the base station. If the instantaneous transmission rate for a given mobile station exceeds the threshold, the weight for that mobile station is incremented by a step. If the instantaneous transmission rate for that mobile station falls below the threshold, the corresponding weight is incremented by a larger step.
Another algorithm, which also seeks to balance throughput against fairness, is the well-known Proportional Fair Scheduling algorithm. Proportional Fair scheduling is discussed, for example, in A. Jalali, et al., “Data Throughput of CDMA-HDR, a High Efficiency Data Rate Personal Communication Wireless System,” Proc. Vehicular Technology Conference VTC 2000, IEEE (2000) 1854-1858.
In Proportional Fair scheduling, the scheduler keeps track of two values, in particular, for each remote terminal: DRC and R. On the downlink of a wireless network, for example, each remote terminal will estimate its SINR for the next timeslot, and on that basis will select a rate for transmission of downlink data from the base station. The selection will typically be the highest available rate consistent with a specified frame error rate, or other such error rate. The transmission rate requested by a given remote terminal in a given timeslot is DRC.
The second value, R, is the rate at which a given remote terminal has received data from the base station, or other hub, as averaged by an appropriate procedure such as exponentially weighted averaging using a desired time constant.
In each timeslot n, the Proportional Fair scheduler will serve that remote terminal for which the ratio
  DRC  Ris greatest. Thus, each remote terminal tends to receive service in those timeslots where its requested rate is highest—not in an absolute sense, but, rather, highest relative to the average rate at which that particular remote terminal has been receiving data in the recent past. Because that average rate will be small for underserved remote terminals, even a remote terminal with a poor channel will eventually be served. That is, the average rates are dynamic quantities, and they will converge toward a condition in which each remote terminal is served reasonably often.
In addition to achieving a balance between throughput and fairness, the Proportional Fair algorithm is attractive because it can be mathematically demonstrated that the long-term throughput achieved using that algorithm, over all remote terminals, satisfies an optimality condition.
However, the Proportional Fair algorithm, among others, does not place any floor or ceiling on the amount of service that a given remote terminal will receive. There remains a need for algorithms that can impose such floors or ceilings, so that, for example, users can contract for different guaranteed levels of service. In particular, there is a need for an efficient scheduling algorithm that seeks to optimize performance according to some measure subject to the imposition of floors, or of floors and ceilings, on the average rates of service to individual terminals.